package gitdemo1.git3.tree;

import gitdemo1.git3.pojo.Tree;

import java.util.*;

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }



    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null){
            return root2;
        }
        if(root2==null){
            return root1;
        }
        TreeNode node = new TreeNode();
        node.val=root1.val+root2.val;
        node.left=mergeTrees(root1.left,root2.left);
        node.right=mergeTrees(root1.right, root2.right);
        return node;

    }

    public static void midOrder(TreeNode node){
          if (node==null){
              return;
          }

          Stack<TreeNode> stack = new Stack<>();
          while(!stack.isEmpty()||node!=null){
              if(node!=null){
                  stack.add(node);
                  node=node.left;
              }else {
                  node=stack.pop();
                  System.out.println(node.val);
                  node=node.right;
              }
          }

      }

    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();

        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                stack.add(root);
                root=root.left;
            }else {
                root = stack.pop();
                list.add(root.val);
                root =root.right;
            }
        }


        return list;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root==null){
            return new ArrayList<>();
        }
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if (node.right!=null){
                stack.add(node.right);
            }
            if(node.left!=null  ){
                stack.add(node.left);
            }
        }


        return list;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //总的集合
        ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
        queue.add(root);
        while (!queue.isEmpty()){
            //小集合
            ArrayList<Integer> arr = new ArrayList<>();
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                    arr.add(node.val);
                    if(node.left!=null){
                        queue.add(node.left);

                    }
                    if(node.right!=null){
                        queue.add(node.right);
                    }
            }
            list.add(arr);

        }
        Collections.reverse(list);

        return list;
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return root.val == sum;
        }

        boolean b = hasPathSum(root.left, sum - root.val);
        boolean a = hasPathSum(root.right, sum - root.val);
        return a||b;

    }

    public int minDepth(TreeNode root) {
          if(root==null){
              return 0;
          }
          int deep1=minDepth(root.left);
          int deep2=minDepth(root.right);
          return Math.min(deep1, deep2)+1;

    }

    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }

        return Math.abs(blanceDepth(root.left)-blanceDepth(root.right))<2&&isBalanced(root.left)&&isBalanced(root.right);
    }

    public int blanceDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int deep1=minDepth(root.left);
        int deep2=minDepth(root.right);

        return Math.max(deep1, deep2)+1;
    }





}
